package DynamicProgrammingPackage;

public class PackageNote2 {
    public static void main(String[] args) {
        // 1. dp[j]表示容量为j的背包的最大价值为dp[j]
        // 2. 递推公式: dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
        // 3. 初始化: dp[0] = 0;非零下标初始化一个不会覆盖掉计算出的数即可dp[j] = 0/-1
        // 4. 遍历顺序: 先遍历物品后遍历背包, 且背包需要倒序遍历
        int[] dp = new int[5];
        int[] weight = new int[]{1,3,5};
        int[] value = new int[]{15,20,30};
        for (int i = 0; i < 5; i++) {
            for (int j = 5; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        };
    }
}
